package com.example.linked;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *  你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 *  示例1：
 * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
 * 输出：[7,8,0,7]
 *
 *  示例2：
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[8,0,7]
 *
 *  示例3：
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 */
public class Leetcode445_AddTwoNumbersII {

    static class Solution {
        /**
         * 解法二:分别将l1, l2翻转之后就转化成了Leetcode2的问题
         * 在此基础上使用头插法生成结果链表即可
         * @param l1
         * @param l2
         * @return
         */
        public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
            ListNode reversedL1 = reverseList(l1);
            ListNode reversedL2 = reverseList(l2);

            ListNode p1 = reversedL1;
            ListNode p2 = reversedL2; // 原链表的两个遍历指针
            ListNode res = new ListNode(-1); // 结果链表的头结点head
            int carry = 0; // 进位
            // 1.遍历两个链表
            while (p1 != null || p2 != null) { // 以⻓长链表为准
                // 获取当前节点的值：链表较短，已⽆无节点，取0
                int x = p1 != null ? p1.val : 0;
                int y = p2 != null ? p2.val : 0;
                // 2.对应位置的节点数值相加
                int sum = x + y + carry;
                carry = sum / 10; // 如何得到进位：和对10求整，得到此次计算的进位
                int num = sum % 10; // 存放到新链表节点中的数值
                // 3.将计算结果插⼊入新链表头部
                ListNode tmp = new ListNode(num); // 创建新节点
                tmp.next = res.next;
                res.next = tmp;
                p1 = p1 == null ? p1 : p1.next;
                p2 = p2 == null ? p2 : p2.next;
            }
            if (carry > 0) { // 处理理进位节点
                ListNode tmp = new ListNode(carry);
                tmp.next = res.next;
                res.next = tmp;
            }
            return res.next;
        }

        private ListNode reverseList(ListNode head) {
            ListNode pre = null;
            ListNode tmp = head, cur = head; // tmp暂存next节点以便下一次遍历不会丢失位置
            while (cur != null) {
                tmp = tmp.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }

        /**
         * 解法一:栈
         * 链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，考虑使用栈：
         * 把所有数字压入栈中，再依次取出相加(结果头插)
         * @param l1
         * @param l2
         * @return
         */
        public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
            Deque<Integer> stack1 = new LinkedList<>();
            Deque<Integer> stack2 = new LinkedList<>();
            // 连个链表的元素分别入栈
            ListNode tmp = l1;
            while (tmp != null) {
                stack1.push(tmp.val);
                tmp = tmp.next;
            }
            tmp = l2;
            while (tmp != null) {
                stack2.push(tmp.val);
                tmp = tmp.next;
            }
            // 计算结果
            int carry = 0;// 标识进位
            ListNode resHead = new ListNode(-1);
            while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
                int num1 = !stack1.isEmpty() ? stack1.pop() : 0;
                int num2 = !stack2.isEmpty() ? stack2.pop() : 0;
                int sum = num1 + num2 + carry;
                carry = sum / 10;
                tmp = new ListNode(sum % 10);
                tmp.next = resHead.next;
                resHead.next = tmp;
            }

            return resHead.next;
        }

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            return addTwoNumbers2(l1, l2);
        }
    }

    public static void main(String[] args) {
        // l1 = [7,2,4,3], l2 = [5,6,4]
        // [7,8,0,7]
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        ListNode res = new Solution().addTwoNumbers(l1, l2);
        ListNode tmp = res;
        while (tmp != null) {
            System.out.println(tmp.val);
            tmp = tmp.next;
        }
    }
}
